#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void append(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    void clear() {
        Node* current = head;
        Node* next = nullptr;
        while (current) {
            next = current->next;
            delete current;
            current = next;
        }
        head = nullptr;
    }

    bool isEmpty() const {
        return head == nullptr;
    }

    LinkedList intersection(const LinkedList& other) const {
        LinkedList result;
        Node* temp1 = head;
        while (temp1) {
            Node* temp2 = other.head;
            while (temp2) {
                if (temp1->data == temp2->data) {
                    result.append(temp1->data);
                    break;
                }
                temp2 = temp2->next;
            }
            temp1 = temp1->next;
        }
        return result;
    }

    LinkedList unionList(const LinkedList& other) const {
        LinkedList result;
        Node* temp = head;
        while (temp) {
            result.append(temp->data);
            temp = temp->next;
        }
        temp = other.head;
        while (temp) {
            if (!result.contains(temp->data)) {
                result.append(temp->data);
            }
            temp = temp->next;
        }
        return result;
    }

    LinkedList difference(const LinkedList& other) const {
        LinkedList res1 = _difference(this, &other);
        LinkedList res2 = _difference(&other, this);
        return res1.unionList(res2);
    }

    static LinkedList _difference(const LinkedList* first, const LinkedList* second) {
        LinkedList result;
        Node* temp = second->head;
        while (temp) {
            if (!first->contains(temp->data)) {
                result.append(temp->data);
            }
            temp = temp->next;
        }
        return result;
    }


private:
    bool contains(int value) const {
        Node* temp = head;
        while (temp) {
            if (temp->data == value) {
                return true;
            }
            temp = temp->next;
        }
        return false;
    }
};

#endif // LINKEDLIST_H
